The interconnection of computers such that programs and data can be shared among a network of computers is presently a subject of much interest. A number of different methods and means for communicating program and/or file data between computers have been devised, and some of these have developed into standards which allow for the interconnection of computer devices which are in compliance with such standards. A specification for one such convention is found in the Institute of Electrical and Electronic Engineers ("IEEE") standard 802.3. This standard specifies the protocol for a Local Area Network ("LAN") communications method which is commonly referred to as "Ethernet" or, more descriptively as "carrier sense, multiple access with collision detection" ("CSMA/CD").
Groups of computers connected via LANs in general and Ethernet in particular can be broken into segments or separate LANs on an application and/or a geographical basis. Each segment or LAN can consist of one or more computers. The segments and LANs may be connected together in a topology by switching elements employing a variety of information forwarding schemes. Each segment of an interconnected LAN is electrically distinct but logically continuous in that information transmitted from one computer to another appears on all segments of a network. Connected LANs are not only electrically distinct but are also logically separate in that information is selectively forwarded from one LAN of an interconnected network to some subset of the other LANs of the network, depending upon the topology of the segments and information forwarding schemes of the network switching elements.
In Ethernet, as in several other computer intercommunication methods, information is communicated in units sometimes referred to as "packets". An Ethernet packet is depicted in FIG. 1 and is designated therein by the general reference character 10. The standardized Ethernet packet 10 has a preamble 12 which is 64 bits in length, a destination address 14 which is 48 bits in length, a source address 16 which is 48 bits in length, a length/type field 18 which is 16 bits in length and a data field 20 which is variable in length from a minimum of 46 eight bit bytes to a maximum of 1500 bytes. Following the data field 20 in the packet 10 is a 4 byte (32 bit) frame sequence check ("FCS") 22. The packet 10 is transmitted serially beginning at a "head" 24 and ending at a "tail" 26 thereof.
In CSMA/CD (Ethernet), computers and switching elements having a packet 10 destined for a particular computer of the network "listen" for the appropriate segment of a LAN to be quiet before transmitting the packet 10. This feature is to avoid interference on the segment and is the "carrier sense" aspect of CSMA/CD. "Multiple access" relates to the distributed nature of the decision making among the computers and switching elements that access a particular LAN.
Despite the carrier sense function it is, nevertheless, possible for more than one computer or switching element to have a packet 10 ready to send to a LAN at precisely the same time. In such an instance, when both units sense quiet on the segment, both begin to transmit at the same time. Each of these transmitting computers and/or switching elements will then detect that a "collision" has occurred and will abort its respective transmission. The resulting incomplete (improperly formed) packets 10 are known as "runts".
Various different types of switching elements have been utilized to electrically interconnect LANs and segments of LANs. For example a "repeater" is a simple switching element which interconnects segments of a LAN. The function of a repeater is merely to receive a data stream from one segment of the LAN and forward it on to the other connected segments of the LAN. The carrier sense and collision detect functions of CSMA/CD take place on all segments of a LAN simultaneously with all computers and switching elements listening for quiet and/or detecting collisions in parallel. All the segments of a LAN interconnected by repeaters are said to be in the same "collision domain", since only one packet 10 can traverse a LAN at a time no matter what is the arrangement of the segments of the LAN. Multiple repeaters can connect numerous segments into a single LAN.
A "bridge" is a somewhat more sophisticated switching element in that it directs data streams between LANs and can, in fact, forward more than one packet 10 at a time with the restriction, discussed above, that only one packet 10 at a time is allowed on each of the connected LANs whether it be transmitting or receiving. Packets received from LANs are directed to their intended destinations by selecting which of the LAN(s) are to receive a particular packet 10. Given the description of the packet 10 previously discussed herein, it can be appreciated that a bridge must have some buffering capability, as it cannot ascertain the intended destination of a packet 10 at least until the destination address 14 is received and interpreted. A so called "standard bridge" receives the packet 10 into its buffer before forwarding it. A "cut through bridge" attempts to speed up the process by beginning to forward the packet 10 before it is fully received (typically, as soon as the destination address 14 is received at the bridge). However, it may not be possible to forward the packet 10 as soon as the destination address 14 is received, since the destination LAN may not be quiet (for example, because another computer or switching element of the destination LAN is transmitting, or for any of various other reasons). Therefore, a bridge should have the capability of buffering substantially more than one packet 10 so that packets 10 can be queued for subsequent sending therefrom. Furthermore, a bridge may be required to retransmit a packet 10 if there is a collision in the destination LAN. This "buffering" in the bridge is required so as to avoid "reflecting" the collision to the source LAN.
The scheme discussed above may seem to be rather simple in description, but it becomes somewhat more complicated in practice. For example, since a number of devices may be competing for access to a particular network LAN there will, as previously mentioned, occur collisions of data resulting in the creation of incomplete packets 10 known as runts. Under heavy load conditions or in a large network, runts can occupy a significant portion of the available network traffic capability. A runt occurs because each device involved in a collision stops transmitting when the collision is detected, generally after only a portion of its packet 10 is transmitted.
A "dumb" bridge attempts to forward all packets 10 which it receives. A "filtering" bridge, on the other hand, attempts to identify packets 10 which, for one reason or another, should not be forwarded to a particular segment. Not forwarding ("filtering out") those packets 10 which should not be forwarded from one LAN to another reduces the traffic overhead in the network leaving more bandwidth available for the complete packets 10 which should be forwarded. This filtering also affects the delay a packet 10 faces in being forwarded to a particular LAN in that the lesser amount of the bandwidth which is being consumed by unwanted packets 10, the more often a packet 10 can be forwarded from a source LAN to a destination LAN immediately (without being queued).
Bridges may "choose" which packets 10 to forward to a particular LAN based on a comparison of the destination address 14 of each packet 10 with some accumulated history data relating to the source addresses 16 of packets 10 previously seen from that LAN. Thus, in the case of a bridge, a packet is (generally) forwarded only to the LAN where the destination address 14 of a packet 10 matches a source address 16 of previous packets 10 seen on that LAN. This "destination address filtering" also reduces traffic on various segments of the network, thus increasing overall performance. Another of the several potential reasons why a packet should not be forwarded is that it is a runt. U.S. Pat. No. 4,679,193 issued to Jensen et al. discloses a Runt Packet Filter for filtering out such runts in particular applications.
It can be appreciated in light of the prior discussion that there exist a number of "trade offs" in the operation of prior art network systems. How much of a packet 10 the bridge must receive prior to beginning to forward the packet 10 is known as the "latency" of the bridge. The longer the latency, the longer is the time delay involved in forwarding a packet 10 and, of course, it is desirable to reduce this delay as much as possible in order to speed up communications. On the other hand, to attempt to reduce this delay by allowing a bridge to begin transmission before an entire packet 10 is received, and thus before the packet 10 can be verified as being a complete packet 10 that should indeed be forwarded, will result in the improper forwarding of at least some packets 10. This, of course, will only slow down the system in that not only is time taken in improperly forwarding a packet 10, but also other packets 10 may be queued behind the improper packet 10 which other packets 10 should and could have been immediately forwarded were the bridge not occupied in forwarding the improper packet 10.
Because of these conflicting considerations, prior art cut through bridges have been designed to provide a latency which allows the bridge to filter out only a relatively small percentage of the improper packets 10. Such prior art filtering, as discussed above, has been accomplished primarily based on characteristics of the packets 10 found in the preamble 12 and/or the destination address 14. Since the preamble 12 and the destination address 14 occur early in the packets 10, the simple prior art filtering scheme does have the advantage that filtering packets 10 based upon these characteristics prevents a significant amount of clogging of the system because many unwanted packets 10 can be quickly and easily rejected for forwarding. However, even after such prior art filtering as is described herein, there remain a great many packets 10 which according to prior art methods are, but should not be, forwarded.
Clearly, it would be desirable to eliminate the forwarding of as many improper packets as possible without increasing latency in the bridge to be longer than is absolutely necessary. However, to the inventors' knowledge, no prior art method has succeeded in optimizing throughput of bridges by providing an optimal bridge latency. Moreover, this problem is exacerbated by the fact that what might be an optimal latency in one application of a bridge might well not be optimal in another application. Indeed, the "optimal" latency may even change in a fixed application as changes are made in the structure or usage of the system.